/**
  \file dawg_gnode.h
  \author Francis Girard
  \date 08 october 2013

  Dawg generator graph node used for generation.
*/


/*
 *  Copyright (C) 2013, Francis Girard
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef __dawg_gnode_h__
#define __dawg_gnode_h__

#include "dawg_arr_node.h"
#include "dawg_arr_unsigned_char.h"
#include "dawg_unique_node_set.h"
#include "dawg_arr_str.h"
#include "dawg_types.h"

#include <stdio.h>

///////////////////////////////////////
///////////////////////////////////////
//                                   //
// extern C BEGIN                    //
//                                   //
///////////////////////////////////////
///////////////////////////////////////
#ifdef __cplusplus
extern "C" {
#endif


/// Handle on a generation node (gnode).
typedef void* h_dawg_gnode;

/**
  Creates an empty dawg node.
*/
h_dawg_gnode dawg_gnode_create_empty();


/**
  Creates a dawg node.
*/
h_dawg_gnode dawg_gnode_create(unsigned char cValue, int depthGroup, h_dawg_gnode hParentNode);


/**
  Destroys a dawg node.
*/
void dawg_gnode_destroy(h_dawg_gnode hNode);


/**
  Determines whether the specified node is an end of word.
  */
dawg_bool_t dawg_gnode_isEow(h_dawg_gnode hNode);


/**
  Determines whether the specified node is an end of child list.
  */
dawg_bool_t dawg_gnode_isEoList(h_dawg_gnode hNode);


/**
  Fetch the character value of the specified node.
  */
unsigned char dawg_gnode_get_cval(h_dawg_gnode hNode);


/**
  Fetch the depth of the specified node.
  */
int dawg_gnode_get_depth(h_dawg_gnode hNode);


/**
  Recursively computes the hash value of this nodes and all of its children.
*/
h_dawg_arr_unsigned_char dawg_gnode_calculate_hash
(
  h_dawg_gnode hNode,
  h_dawg_arr_unsigned_char hBrothersHash
);


/**
  Recursively linearize the tree structure starting at the specified root.

  The specified root node itself is excluded.
*/
void dawg_gnode_index_nodes(h_dawg_gnode h_root, h_dawg_arr_node hIndexedNodes);


/**
  Recursively mark the first and last childs (in their parent's list).
*/
void dawg_gnode_mark_first_and_last_child(h_dawg_gnode hNode);


/**
  Find all the nodes with the requested depth.

  Note that during or after reduction, a node may have
  more than one parent and therefore, if we simply and
  classical traverse the tree, the exact same node may
  occur twice. Therefore we store them into a "unique set".
*/
void dawg_gnode_find_nodes_at_depth(h_dawg_gnode hNode, int depth, h_dawg_unique_node_set result);


/**
  Determines whether the two specified nodes have the hash value.
*/
dawg_bool_t dawg_gnode_same_hash(h_dawg_gnode hNode1, h_dawg_gnode hNode2);


/**
  Get the siblings at the right of the specified node, that specified node included.
*/
void dawg_gnode_get_right_siblings(h_dawg_gnode hNode, h_dawg_arr_node hOutArray);


/**
  Blindly substitute a direct child for another.
  @param hParentNode The parent node for which we want to substitute a child.
  @param hChildNodeToRm The child node that must be substituted.
  @param hChildNodeReplaceant The new child node that should replace "hChildNodeToRm".
  @return True iff the child node to substitute has been found and substituted.
  */
dawg_bool_t dawg_gnode_substitute_child(h_dawg_gnode hParentNode,
                                        h_dawg_gnode hChildNodeToRm,
                                        h_dawg_gnode hChildNodeReplaceant);


/**
  Adds the specified new parents to the specified node.

  That is it only adds the new parents to its internal parent's list without
  taking care of the rest of the tree.
  */
void dawg_gnode_add_parents(h_dawg_gnode hNode, h_dawg_arr_node hArrNewParents);


/**
  Substitute a node with another when they are equivalent.
  */
void dawg_gnode_reduce_node(h_dawg_gnode hToRm, h_dawg_gnode hNodeSubstitute);


/**
  Binary encoding of the specified node on 4 bytes.
  @return The encoded value of the node.
*/
int dawg_gnode_encoded(h_dawg_gnode hNode);


/**
  Find a direct child with the specified character value.
*/
h_dawg_gnode dawg_gnode_find_child(h_dawg_gnode hNode, unsigned char childValue);


/**
  Get the number of direct childs.
*/
unsigned int dawg_gnode_get_nb_childs(h_dawg_gnode hNode);


/**
  Adds a new child value to the specified node.
*/
h_dawg_gnode dawg_gnode_add_child(h_dawg_gnode h_parent_node, unsigned char childValue, int depthGroup);


/**
  Builds a classical trie (prefix tree) from the specified list of words.

  @param h_input_words The list of words ordered by length and then alphabetically.
  @return The root node.
*/
h_dawg_gnode dawg_gnode_build_trie(h_dawg_gnode h_root_node, h_dawg_arr_str h_input_words);


void dawg_gnode_reduce_graph(h_dawg_gnode hRootNode, int nMaxNodeDepth);


/**
  Determines whether the specified node has a child.
*/
dawg_bool_t dawg_gnode_has_child(h_dawg_gnode hNode);


/**
  Get the character value of the specified node.
*/
unsigned char dawg_gnode_get_value(h_dawg_gnode hNode);


/**
  Index difference between the specified node and its first child.
*/
int dawg_gnode_get_diff_index_with_fst_child(h_dawg_gnode hNode);


/**
  Prints the tree the root of which is specified and into the specified out stream.
*/
void dawg_gnode_print(h_dawg_gnode hNodeRoot, FILE* pOutFile);


///////////////////////////////////////
///////////////////////////////////////
//                                   //
// extern C END                      //
//                                   //
///////////////////////////////////////
///////////////////////////////////////
#ifdef __cplusplus
}
#endif

// #ifndef __dawg_gnode_h__
#endif
